package main

import (
	"fmt"
)

/**
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

子数组最大值等于数组各个位置结尾的数组的最大值
我们定义以位置i结尾的最大的序列值为maxToCurrent，全部连续序列中最大的值为max，那么max = Max(maxToCurrent(0),maxToCurrent(1)...maxToCurrent(n-1))
max和maxToCurrent关系搞清楚了，那么我们需要知晓的是maxToCurrent如何得来
maxToCurrent(n) = Max(maxToCurrent(n-1)+num[n],num[n]),我们知晓maxTocurrnet(0),那么便可依次递推到maxToCurrent(n)


*/

func main() {
	fmt.Println(maxSubArray([]int{-2, 1}))
}

func maxSubArray(nums []int) int {
	if len(nums) == 0 {
		return 0
	} else if len(nums) == 1 {
		return nums[0]
	} else {
		dp := make(map[int]int)
		dp[0] = nums[0]
		m := nums[0]
		for i := 1; i < len(nums); i++ {
			dp[i] = max(nums[i]+dp[i-1], nums[i])
			m = max(m, dp[i])
		}
		return m
	}

}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}
